package chapter_05;


/*
链表的效率
（双端链表）在表头插入和删除速度很快。仅需要改变一两个引用值，所以花费O(1)的时间。
平均起来，查找、删除和在指定节点后面插入都需要搜索链表中的一半节点。需要O(N)次比较。
在数组中执行这些操作也需要O(N)次比较，但是链表仍然要快一些，因为当插入和删除节点时，
链表不需要移动任何东西。增加的效率是很显著的，特别是当复制时间远远大于比较时间的
时候。
当然，链表比数组优越的另一个重要方面是链表需要多少内存就可以用多少内存，并且可以
扩展到所有可用内存。数组的大小在它创建的时候就固定了；所以经常由于数组太大导致效率低下，
或者数组太小导致空间溢出。向量是一种可扩展的数组，它可以通过可变长度解决这个问题，但是
它经常只允许以固定大小的增量扩展（例如快要溢出的时候，就增加一倍数组容量）。这个解决方
案在内存使用效率上来说还是要比链表低。
 */


/*
数据类型和抽象
● 数据类型
数据类型一词用在很多地方。它首先表示内置的类型，例如int型和double型。也有用户自己定义
的类型。

● 抽象
抽象这个词的意思是“不考虑细节的描述和实现”。抽象是事物的本质和重要特征。例如，总
统办公室是一个抽象，它并不考虑哪一个人碰巧称为这个办公室的主人。总统办公室的权力和责任
依旧，但是总统会随着任职和去职而来去。
因此，在面向对象编程中，一个抽象数类型是一个类，且不考虑它的实现。它是对类中数据
（域）的描述和能够在数据上执行的一系列操作（方法）以及如何使用这些操作的说明。每个方法
如何执行任务的细节肯定不包括在内。作为类的用户，只会被告知可以调用哪些方法，如何调用它
们，以及渴望得到的结果，但是不包括内部如何运作的。

● 接口
ADT经常有一个经常叫做“接口”的规范。它是给类用户看的，通常是类的公有方法。在栈中，
push()方法、pop()方法和其他类似的方法形成了接口。

● ADT线性表
线性表是一组线性排列的数据项，也就是说，它们以一定的方式串接起来，像一根线上的珠子或
一条街上的房子。线性表支持一定的基本操作。可以插入某一项，删除某一项，还有经常从某个
特定位置读出一项。
线性表由它的接口定义：即用于和它交互的特定方法。这个接口可以用不同的结构实现，包括数
组、链表。线性表是这些数据结构的抽象。
 */


/*
双向链表
在双向链表中，Link类定义的开头是这样声明的：
class Link {
    public long dData;
    public Link next;
    public Link previous;
    ...
}
双向链表的缺点是每次插入或删除一个节点的时候，要处理四个节点的引用，而不是两个：
两个连接前一个节点，两个连接后后一个节点。当然，由于多了两个引用，节点的占用空间也
变大了一点。
双向链表不必是双端链表（保持一个对链表最后一个元素的引用），但这种方式是有用的，所以在
后面的例子中将包含双端的性质。

遍历
两个显示方法说明了双向链表的遍历。displayForward()方法和在普通链表中看到的displayList()
方法一样。displayBackward()方法与它们类似，但是从表尾开始，通过每个元素的previous域，一
步一步向前到达表头。下面这段代码显示了这一过程：
Link current = last;
while (current != null)
    current = current.previous
 */

public class chapter_05
{
}
